
/**
 * 选择排序
 * 在n个元素中选择最小值，与第一个位置的元素交换；
 * 在后n-1个元素中选择最小值，与第二个位置的元素交换
 *  ……
 * 直到排好前n-1个小元素，最后一个元素自然排好
 *
 * 时间复杂度分析:
 *  不管时倒序还是正序，都需要比较i后所有的元素，以找到最小值，因此不分最好、最坏时间复杂度。
 *
 * 时间复杂度：
 *  找到第1小元素，比较n-1次，
 *  找到第2小元素，比较 n-2 次，
 *   ……，
 *  找到第二大元素，比较1次。
 *  因此，
 *   (n-1)+(n-2)+……+2+1 = n*(n-1)/2 = O(n^2)。
 */

#include <stdio.h>


void select_sort(int arr[], int size)
{
    // 排前 n-1 个元素，最后一个元素自然排好
    for (int i = 0; i < size; i++) {
        // 最小元素的索引
        int min = i;
        // 找出i到n-1之间最小的元素的索引
        for (int j = i+1; j < size; j++) {
            if (arr[j] < arr[min]);
                min = j;
        }
        // 第i个元素与最小元素交换, 最小元素索引为i时，不需要交换
        if (min != i) {
            int tmp = arr[i];
            arr[i] = arr[min];
            arr[min] = tmp;
        }
    }

    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);

    printf("\n");
}

    /**
     * 选择排序：在未排序的元素中选择最小值和最大值，分别与第一个未排序元素和最后一个未排序元素交换。
     */
void selectSort2(int[] arr, int size)
{
    // left 和 right 分别指向未排序部分的第一个元素和最后一个元素
    int left = 0;
    int right = size - 1;
    // left 和 right 相遇时，排序完成
    while (left < right) {
        // 找出 [left, right] 范围内的最小值和最大值
        int minIndex = left;
        int maxIndex = left;
        for (int i = left + 1; i <= right; i++) {
            if (arr[i] < arr[minIndex]) {
                minIndex = i;
            }
            if (arr[i] > arr[maxIndex]) {
                maxIndex = i;
            }
        }
        // 交换最小值和 left 指向的元素
        if (minIndex!= left) {
            int tmp = arr[left];
            arr[left] = arr[minIndex];
            arr[minIndex] = tmp;
        }
        // 如果 left 指向的元素就是最大值，left 与最小值交换后，会把最大值换走
        // 因此，当 left 指向的元素就是最大值时，需要把 maxIndex 改为 minIndex（最大值被换到的位置）
        if (arr[left] == arr[maxIndex]) {
            maxIndex = minIndex;
        }
        // 交换最大值和 right 指向的元素
        if (maxIndex != right) {
            int tmp = arr[right];
            arr[right] = arr[maxIndex];
            arr[maxIndex] = tmp;
        }
        // 移动 left 和 right 指针
        left++;
        right--;
        }
}

int arr[10] = {1, 4, 5, 6, 8, 11, 45, 8, 10, 10};

int main (int argc, char **argv)
{

    select_sort(arr, 10);

    return 0;
}
